#include <iostream>
#include <stack>
#include <vector>
using namespace std;

//剑指 Offer 30. 包含min函数的栈
class MinStack {
public:
    
    void push(int x) {
        _st.push(x);
        if (_min.empty() || _st.top() <= _min.top())
        {
            _min.push(x);
        }
    }
    
    void pop() {
        if (_st.top() == _min.top())
        {
            _min.pop();
        }
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int min() {
        return _min.top();
    }

private:
    stack<int> _st;
    stack<int> _min;
};



struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:

    //剑指 Offer 06. 从尾到头打印链表
    void dfs(vector<int>& ans, ListNode* cur)
    {
        if (cur == nullptr)
        {
            return;
        }
        dfs(ans, cur->next);
        ans.push_back(cur->val);
    }

    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        dfs(ans, head);
        return ans;
    }
///////////////////////////////////////////////////////
    //剑指 Offer 24. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

///////////////////////////////////////////////////////
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

    //剑指 Offer 35. 复杂链表的复制
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        while (cur != nullptr)
        {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }
        cur = head;
        while (cur != nullptr)
        {
            cur->next->random = cur->random ? cur->random->next : nullptr;
            cur = cur->next->next;
        }
        cur = head;
        Node* guard = new Node(-1);
        Node* del = guard;

        while (cur != nullptr)
        {
            guard->next = cur->next;
            guard = guard->next;

            cur->next = guard->next;
            cur = cur->next;
        }
        guard = del->next;
        delete del;
        return guard;
    }
///////////////////////////////////////////////////////
};

// class A
// {
// public:
//     A()
//     {
//         cout << "A::A()" << endl;
//     }
// private:
//     int _a1;
//     int _a2;
//     int _a3;
//     int _a4;
// };

// class B : public A
// {
// public:
//     B()
//     {
//         cout << "B::B()" << endl;
//     }
// private:
//     // int _b1;
//     // int _b2;
//     // int _b3;
//     // int _b4;
// };

// int main()
// {
//     //A a;
//     B b;
    
//     cout << sizeof(A) << endl;
//     cout << sizeof(B) << endl;
//     return 0;
// }